Video compression utilizes block processing for many operations. In block processing, a block of neighboring pixels is grouped into a coding unit and compression operations treat this group of pixels as one unit to take advantage of correlations among neighboring pixels within the coding unit. Block-based processing often includes prediction coding and transform coding. Transform coding with quantization is a type of data compression which is commonly “lossy” as the quantization of a transform block taken from a source picture often discards data associated with the transform block in the source picture, thereby lowering its bandwidth requirement but often also resulting in lower quality reproduction of the original transform block from the source picture.
MPEG-4 AVC, also known as H.264, is an established video compression standard utilizing transform coding in block processing. In H.264, a picture is divided into macroblocks (MBs) of 16×16 pixels. Each MB is often further divided into smaller blocks. Blocks equal in size to or smaller than a MB are predicted using intra-/inter-picture prediction, and a spatial transform along with quantization is applied to the prediction residuals. The quantized transform coefficients of the residuals are commonly encoded using entropy coding methods (i.e., variable length coding or arithmetic coding). Context Adaptive Binary Arithmetic Coding (CABAC) was introduced in H.264 to provide a substantially lossless compression efficiency by combining an adaptive binary arithmetic coding technique with a set of context models. Context model selection plays a role in CABAC in providing a degree of adaptation and redundancy reduction. H.264 specifies two kinds of scan patterns over 2D blocks. A zigzag scan is utilized for pictures coded with progressive video compression techniques and an alternative scan is for pictures coded with interlaced video compression techniques.
H.264 uses 2D block-based transform of block sizes 2×2, 4×4 and 8×8. A block-based transform converts a block of pixels in spatial domain into a block of coefficients in transform domain. Quantization then maps transform coefficients into a finite set. After quantization, many high frequency coefficients become zero. For a block having at least one non-zero coefficient after 2D transform and quantization operation, a significance map is developed, which specifies the position(s) of the non-zero quantized coefficient(s) within the 2D transform domain. Specifically, given a quantized 2D transformed block, if the value of a quantized coefficient at a position (y, x) is non zero, it is considered as significant and a “1” is assigned for the position (y, x) in the associated significance map. Otherwise, a “0” is assigned to the position (y, x) in the significance map. In
H.264, CABAC is used for coding and decoding each element of the significance map.
HEVC (High Efficiency Video Coding), an international video coding standard being developed to succeed H.264, extends transform block sizes to 16×16 and 32'32 pixels to benefit high definition (HD) video coding. In the models under consideration for HEVC, a set of transform coefficient coding and decoding tools can be enabled for entropy coding and decoding. Among these tools is an adaptive scan scheme, which is applied for significance map coding and decoding. This scheme adaptively switches between two scan patterns for coding and decoding a significance map if the significance map array size is larger than 8×8.
The adaptive scan scheme directs the scan order for coding and decoding a significance map by switching between two predefined scan patterns per diagonal line, either from bottom-left to top-right or from top-right to bottom-left diagonally. The switching occurs at the end of each diagonal sub-scan, and is controlled by two counters. The first counter, c1, tracks the number of coded significant transform coefficients located in the bottom-left half of a transform block. The second counter, c2, tracks the number of coded significant transform coefficients which are located in the top-right half of a transform block. The implementation of the models considered for HEVC with using two scan patterns and two counters introduces substantial computational complexity and additional memory requirements. These complexities include tracking the count of coded significant transform coefficients located in the bottom-left half or in the top-right half of a transform, performing branch operations and making scan selections for coefficients in significance map coding and decoding. On the other hand, the adaptive scan scheme achieves only a negligible performance gain. Or, it provides no substantial gain in reducing bandwidth requirements for compression data associated with transform processing.